/*
 * Question: Given the conditions as the 33rd exercise, but an
 * additional array T is provided to store the parents of all
 * nodes. In other words, the T[i] indicates the parent of i.
 * Try to resolve the same problem as the 33rd exercise with
 * array T.
 */

#include <iostream>
#include <fstream>
#include <stack>
#include "iofile.h"
#include "sqlist.h"
using namespace std;

class sqlist : public _sqlist<int> {};

sqlist L, R, T;

/*
 * Starting from u, we obtain the parent of u by T, say P1. And
 * then, we obtain the parent of P1 again, say P2, and so forth.
 * The process continues until we hit the root of tree, or some
 * node is indentical to v. The fomer implies that v is not a
 * acestor of u, while the latter suggests that v does.
 */
bool is_descendent(int u, int v)
{
    int p;

    if (u == v)
        return false;

    T.elem[1] = 0;
    for (int i = 1; i <= L.len; i++) {
        if (L.elem[i]) T.elem[L.elem[i]] = i;
        if (R.elem[i]) T.elem[R.elem[i]] = i;
    }

    for (p = u; p && p != v; p = T.elem[p])
        ;
    if (p == v)
        return true;
    else
        return false;
}

int main()
{
    int u, v;

    open_input("chap06/ex34.txt");
    sqlist_create<sqlist, int>(L);
    sqlist_create<sqlist, int>(R);
    cout << "ancestor = ";
    cin >> v;
    cout << "descendent = ";
    cin >> u;
    if (is_descendent(u, v))
        cout << "yes" << endl;
    else
        cout << "no" << endl;
    close_input();
    return 0;
}
